LeetCode 231. Power of Two

231. Power of Two(2的幂)

链接

https://leetcode-cn.com/problems/power-of-two

题目

给定一个整数,编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 20 = 1
示例 2:

输入: 16
输出: true
解释: 24 = 16
示例 3:

输入: 218
输出: false

思路

位运算,算是做之前不知道咋做,做了后就熟了的题目,代码也都简单,有两个式子。
先得知,若为二的幂,转换为二进制之后只有一位数字是1,别的数字都是0.

  1. (n > 0) && ((n & -n) == n)
    负数补码的存放是取反加一,假设为8,整数为1000,负数-8,为0111+0001=1000(取反加一),二者&运算,结果为1000,还是8.

  2. (n > 0) && ((n & (n - 1)) == 0)
    同样用8举例,n-1=7为0111,二者&运算,结果为0.

两个式子的运算耗时差距也不是很大,看能想起来哪个吧,主要就是记得二进制是特殊的,适合位运算就行。

代码

1
2
3
4
public static boolean isPowerOfTwo(int n) {
return (n > 0) && ((n & -n) == n);
// return (n > 0) && ((n & (n - 1)) == 0);
}
---本文结束,感谢阅读---